/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *tmpA = headA, *tmpB = headB;
        while (tmpA != tmpB)
        {
            tmpA = tmpA == nullptr ? headB : tmpA->next;
            tmpB = tmpB == nullptr ? headA : tmpB->next;
        }
        return tmpA;
    }
};

/*class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int n1 = 0, n2 = 0;
        ListNode *tmpA = headA, *tmpB = headB;
        while(tmpA)
        {
            ++n1;
            tmpA = tmpA->next;
        }
        while(tmpB)
        {
            ++n2;
            tmpB = tmpB->next;
        }
        tmpA = headA, tmpB = headB;
        int diff = abs(n1 - n2);
        while(diff--) // 长的走diff步
        {
            if(n1 > n2)
                tmpA = tmpA->next;
            else
                tmpB = tmpB->next;
        }
        while(tmpA != tmpB) // tmpA同时为空也是相等
        {
            tmpA = tmpA->next;
            tmpB = tmpB->next;
        }
        return tmpA;
    }
};*/